<?php
class TreeNode {
    public $val = null;
    public $left = null;
    public $right = null;
    function __construct($value) {
        $this->val = $value;
    }
}

class Solution {
    public function lowestCommonAncestor($root, $p, $q) {
        // Value of current node or parent node.
        $parentVal = $root->val;

        // Value of p
        $pVal = $p->val;

        // Value of q;
        $qVal = $q->val;

        if ($pVal > $parentVal && $qVal > $parentVal) {
            // If both p and q are greater than parent
            return $this->lowestCommonAncestor($root->right, $p, $q);
        } else if ($pVal < $parentVal && $qVal < $parentVal) {
            // If both p and q are lesser than parent
            return $this->lowestCommonAncestor($root->left, $p, $q);
        } else {
            // We have found the split point, i.e. the LCA node.
            // 一大一小
            return $root;
        }
    }

    public function lowestCommonAncestorV1($root, $p, $q) {
        // Value of p
        $pVal = $p->val;

        // Value of q;
        $qVal = $q->val;

        $node = $root;

        while ($node != null) {
            if ($pVal > $node->val && $qVal > $node->val) {
                // If both p and q are greater than parent
               $node = $node->right;
            } else if ($pVal < $node->val && $qVal < $node->val) {
                // If both p and q are lesser than parent
                $node = $node->left;
            } else {
                // We have found the split point, i.e. the LCA node.
                // 一大一小
                return $node;
            }
        }
    }
}